package com.leetcode.LC;

import java.util.ArrayList;

public class LC1071 {
    public String gcdOfStrings(String str1, String str2) {
        if (str1.split(str2).length == 0) {
            return str2;
        }
        ArrayList<String> list = new ArrayList<>();
        for (int i = 1; i <= str2.length() / 2; i++) {
            if (str2.split(str2.substring(0, i)).length == 0) {
                list.add(str2.substring(0, i));
            }
        }

        for (int i = list.size() - 1; i >= 0; i--) {
            if (str1.split(list.get(i)).length == 0) {
                return list.get(i);
            }
        }
        return "";
    }

    public String gcdOfStrings2(String str1, String str2) {
        // 假设str1是N个x，str2是M个x，那么str1+str2肯定是等于str2+str1的。
        if (!(str1 + str2).equals(str2 + str1)) {
            return "";
        }
        // 辗转相除法求gcd。
        return str1.substring(0, gcd(str1.length(), str2.length()));
    }

    private int gcd(int a, int b) {
        return b == 0? a: gcd(b, a % b);
    }

    public static void main(String[] args) {
        //System.out.println("ABCABC".split("AB").length);
        System.out.println(new LC1071().gcdOfStrings("ABABABAB", "ABAB"));
    }
}
